#ifndef cathlibcpp_set_H
#define cathlibcpp_set_H

// File:       set.h
// Author:     (c) Miles Sabin, 1997
// Purpose:    approximation to ANSI C++ set and multiset class templates


#ifndef cathlibcpp_assocbase_H
#include "assocbase.h"
#endif

#ifndef cathlibcpp_bool_H
#include "bool.h"
#endif

#ifndef cathlibcpp_config_H
#include "config.h"
#endif

#ifndef cathlibcpp_iterator_H
#include "iterator.h"
#endif

#ifndef cathlibcpp_newcasts_H
#include "newcasts.h"
#endif

#ifndef cathlibcpp_utility_H
#include "utility.h"                 // for pair<T1, T2>
#endif


#ifdef PROBLEM_LONG_NAMES

// abbreviations to stop CFront choking on long names

#define set_const_iterator           __sci

#endif


// class set<Key, Compare>

#define set_iterator                 set_const_iterator

template<class Key, class Compare>
class set_const_iterator;


template<class Key, class Compare>
class set
{
  friend bool operator==(set<Key, Compare> const& x, set<Key, Compare> const& y);
  friend bool operator< (set<Key, Compare> const& x, set<Key, Compare> const& y);

  public:

#   define set_type                  set<Key, Compare>
#   define key_type                  Key
#   define value_type                Key
#   define reference                 Key&
#   define const_reference           Key const&
#   define iterator                  set_iterator<Key, Compare>
#   define const_iterator            set_const_iterator<Key, Compare>
#   define rev_iterator              reverse_bidirectional_iterator<iterator, value_type, value_type const&>
#   define const_rev_iterator        reverse_bidirectional_iterator<const_iterator, value_type, value_type const&>
#   define size_type                 size_t
#   define difference_type           ptrdiff_t

    // constructors
    set();
    set(Compare const& cmp);
    set(iterator const& first, iterator const& last);
    set(iterator const& first, iterator const& last, Compare const& cmp);
    set(value_type const* first, value_type const* last);
    set(value_type const* first, value_type const* last, Compare const& cmp);
    set(set<Key, Compare> const& rhs);
    ~set();

    // accessors
    const_iterator begin() const;
    const_iterator end() const;

    const_rev_iterator rbegin() const;
    const_rev_iterator rend() const;

    bool empty() const;
    size_type size() const;
    size_type max_size() const;

    const_iterator find(key_type const& x) const;

    size_type count(key_type const& x) const;

    const_iterator lower_bound(key_type const& x) const;
    const_iterator upper_bound(key_type const& x) const;
    pair<const_iterator, const_iterator> equal_range(key_type const& x) const;

    Compare key_compare() const;

    // mutators
    set<Key, Compare>& operator=(set<Key, Compare> const& rhs);

    iterator begin();
    iterator end();

    rev_iterator rbegin();
    rev_iterator rend();

    pair<iterator, bool> insert(value_type const& x);
    iterator insert(iterator const& hint, value_type const& x);
    void insert(iterator const& first, iterator const& last);
    void insert(value_type const* first, value_type const* last);

    void erase(iterator position);
    size_type erase(key_type const& x);
    void erase(iterator first, iterator last);

    void swap(set<Key, Compare>& x);

    void clear();

    iterator find(key_type const& x);

    iterator lower_bound(key_type const& x);
    iterator upper_bound(key_type const& x);
    pair<iterator, iterator> equal_range(key_type const& x);

  private:

    Compare key_cmp_;
    assoc_base tree_;

#   undef set_type
#   undef key_type
#   undef value_type
#   undef reference
#   undef const_reference
#   undef iterator
#   undef const_iterator
#   undef rev_iterator
#   undef const_rev_iterator
#   undef size_type
#   undef difference_type
};


template<class Key, class Compare>
bool operator==(set<Key, Compare> const& lhs, set<Key, Compare> const& rhs);

template<class Key, class Compare>
bool operator< (set<Key, Compare> const& lhs, set<Key, Compare> const& rhs);


// class multiset<Key, Compare>

#define multiset_iterator            multiset_const_iterator
#define multiset_const_iterator      set_const_iterator


template<class Key, class Compare>
class multiset
{
  friend bool operator==(multiset<Key, Compare> const& x, multiset<Key, Compare> const& y);
  friend bool operator< (multiset<Key, Compare> const& x, multiset<Key, Compare> const& y);

  public:

#   define multiset_type             multiset<Key, Compare>
#   define key_type                  Key
#   define value_type                Key
#   define reference                 Key&
#   define const_reference           Key const&
#   define iterator                  multiset_iterator<Key, Compare>
#   define const_iterator            multiset_const_iterator<Key, Compare>
#   define rev_iterator              reverse_bidirectional_iterator<iterator, value_type, value_type const&>
#   define const_rev_iterator        reverse_bidirectional_iterator<const_iterator, value_type, value_type const&>
#   define size_type                 size_t
#   define difference_type           ptrdiff_t

    // constructors
    multiset();
    multiset(Compare const& cmp);
    multiset(iterator const& first, iterator const& last);
    multiset(iterator const& first, iterator const& last, Compare const& cmp);
    multiset(value_type const* first, value_type const* last);
    multiset(value_type const* first, value_type const* last, Compare const& cmp);
    multiset(multiset<Key, Compare> const& rhs);
    ~multiset();

    // accessors
    const_iterator begin() const;
    const_iterator end() const;

    const_rev_iterator rbegin() const;
    const_rev_iterator rend() const;

    bool empty() const;
    size_type size() const;
    size_type max_size() const;

    const_iterator find(key_type const& x) const;

    size_type count(key_type const& x) const;

    const_iterator lower_bound(key_type const& x) const;
    const_iterator upper_bound(key_type const& x) const;
    pair<const_iterator, const_iterator> equal_range(key_type const& x) const;

    Compare key_compare() const;

    // mutators
    multiset<Key, Compare>& operator=(multiset<Key, Compare> const& rhs);

    iterator begin();
    iterator end();

    rev_iterator rbegin();
    rev_iterator rend();

    pair<iterator, bool> insert(value_type const& x);
    iterator insert(iterator const& hint, value_type const& x);
    void insert(iterator const& first, iterator const& last);
    void insert(value_type const* first, value_type const* last);

    void erase(iterator position);
    size_type erase(key_type const& x);
    void erase(iterator first, iterator last);

    void swap(multiset<Key, Compare>& x);

    void clear();

    iterator find(key_type const& x);

    iterator lower_bound(key_type const& x);
    iterator upper_bound(key_type const& x);
    pair<iterator, iterator> equal_range(key_type const& x);

  private:

    Compare key_cmp_;
    assoc_base tree_;

#   undef multiset_type
#   undef key_type
#   undef value_type
#   undef reference
#   undef const_reference
#   undef iterator
#   undef const_iterator
#   undef rev_iterator
#   undef const_rev_iterator
#   undef size_type
#   undef difference_type
};


template<class Key, class Compare>
bool operator==(multiset<Key, Compare> const& lhs, multiset<Key, Compare> const& rhs);

template<class Key, class Compare>
bool operator< (multiset<Key, Compare> const& lhs, multiset<Key, Compare> const& rhs);


// set_const_iterator

template<class Key, class Compare>
class set_const_iterator : public bidirectional_iterator<Key const>
{
  friend class set<Key, Compare>;
  friend class multiset<Key, Compare>;

  public:

    // constructors
    set_const_iterator()
      {}
    set_const_iterator(set_const_iterator<Key, Compare> const& rhs);

    // accessors
    bool operator==(set_const_iterator<Key, Compare> const& rhs) const
      { return node_ == rhs.node_; }

    Key const& operator*() const
      { return *reinterpret_cast(Key const*, node_+1); }

    // mutators
    set_const_iterator<Key, Compare>& operator=(set_const_iterator<Key, Compare> const& rhs);

    set_const_iterator<Key, Compare>& operator++();
    set_const_iterator<Key, Compare> operator++(int);

    set_const_iterator<Key, Compare>& operator--();
    set_const_iterator<Key, Compare> operator--(int);

  private:

    set_const_iterator(assoc_base const* tree, assoc_base_node const* node)
      : tree_(tree),
        node_(node)
      {}

    assoc_base const* tree_;
    assoc_base_node const* node_;
};

#endif
